home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / gems / g_gemsii.lha / GemsII / BitCounting / bit32.c next >
Encoding:
Text File  |  1991-08-26  |  2.0 KB  |  59 lines
  1. /*
  2.  * bit32on - count the 1 bits in a 32-bit long integer. Three varients are
  3.  *           provided (the second accepts further code revision); one will
  4.  *           be ``best'' based on the nature of the data and the hardware.
  5.  *           Use of "register" directives may also yield further speed-up.
  6.  *           The user is urged to perform comparative analysis for a given
  7.  *           architecture and to study the assembler output, or to hand code.
  8.  *           This code has been thoroughly tested by the second author.
  9.  *
  10.  * Alan W. Paeth
  11.  * David Schilling
  12.  */
  13.  
  14. int bit32on1(a)
  15.   unsigned long a;
  16.   {
  17.   int c;
  18.   c = 0;
  19.   while( a != 0 )       /* until no bits remain, */
  20.     {
  21.     c++;                /* "tally" ho, then */
  22.     a = a &~ -a;        /* clear lowest bit */
  23.     }
  24.   return(c);
  25.   }
  26.  
  27. int bit32on2(a)
  28.   unsigned long a;                              /* a: 32  1-bit tallies */
  29.   {
  30.   a = (a&0x55555555) + ((a>>1) &(0x55555555));  /* a: 16  2-bit tallies */
  31.   a = (a&0x33333333) + ((a>>2) &(0x33333333));  /* a:  8  4-bit tallies */
  32.   a = (a&0x07070707) + ((a>>4) &(0x07070707));  /* a:  4  8-bit tallies */
  33. /* a %= 255; return(a); may replace what follows */
  34.   a = (a&0x000F000F) + ((a>>8) &(0x000F000F));  /* a:  2 16-bit tallies */
  35.   a = (a&0x0000001F) + ((a>>16)&(0x0000001F));  /* a:  1 32-bit tally */
  36.   return(a);
  37.   }
  38.  
  39. int bit32on3(a)
  40.     unsigned long a;
  41.     {
  42.     unsigned long mask, sum;
  43.     if (a == 0)                 /* a common case */
  44.         return(0);
  45.     else if (a == 0xffffffff)   /* ditto, but the early return is essential: */
  46.         return(32);             /* it leaves mod 31 (not 33) final states */
  47.     mask = 0x42108421L;
  48.     sum = a & mask;             /* 5x: accumulate through a 1-in-5 sieve */
  49.     sum += (a>>=1) & mask;
  50.     sum += (a>>=1) & mask;
  51.     sum += (a>>=1) & mask;
  52.     sum += (a>>=1) & mask;
  53.     sum %= (mask = 31);         /* casting out mod 31 (save that constant) */
  54.     return(sum ? sum : mask);   /* return bits (zero indicated 31 bits on) */
  55.     }
  56.  
  57.  
  58.  
  59.